package 剑指offer;

import sun.security.util.Length;

import java.util.List;

public class 剑指Offer077链表排序 {
    public static void main(String[] args) {
        ListNode node4 = new ListNode(3,null);
//        ListNode node3 = new ListNode(1,node4);
        ListNode node2 = new ListNode(2,node4);
        ListNode node1 = new ListNode(4,node2);
        剑指Offer077链表排序 o = new 剑指Offer077链表排序();
        ListNode listNode = o.sortList(node1);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }



    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //快慢指针找中点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //循环结束，找到中点
        ListNode temp = slow.next;//使用一个节点用来保存中间节点的后一个节点
        slow.next = null;//断开前后两段节点

        ListNode prev = sortList(head);       //创建一个新的节点，用来保存前一半节点的排序后的节点。
        ListNode end = sortList(temp);        //创建一个新的节点，用来保存后一半节点的排序后的节点。

        ListNode dummyHead = new ListNode();
        ListNode dummy = dummyHead;
        while (prev != null && end != null){
            if (prev.val <= end.val){//前面节点值小
                dummy.next = prev;
                prev = prev.next;
                dummy = dummy.next;
            }else {
                dummy.next = end;
                end = end.next;
                dummy = dummy.next;
            }
        }
        dummy.next = prev == null ? end : prev;
        return dummyHead.next;
    }
}
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
